#ifdef LOCAL
#include <bits/stdc++.h>
using namespace std;
#endif

class Solution {
public:
    bool wordBreak(string s, vector<string>& wordDict) {
        unordered_set<string> wordSet(wordDict.begin(),wordDict.end());
        vector<bool> memory(s.size(),true);
        return dfs(s,wordSet,memory,0);
    }

    bool dfs(const string &s,unordered_set<string> &wordSet,vector<bool> &memory,int startIndex){
        if(startIndex>=s.size()) return true;
        if(!memory[startIndex]) return true;
        for(int i=startIndex;i<s.size();i++){
            string word = s.substr(startIndex,i-startIndex+1);
            if(wordSet.count(word) && dfs(s,wordSet,memory,i+1)) return true;
        }
        memory[startIndex] = false;
        return false;
    }
};

#ifdef LOCAL
#include <windows.h>
int main() {
    Solution solution;
    string s = "leetcode";
    vector<string> wordDict{"leet", "code"};
    clock_t startTime, endTime;
    startTime = clock();
    cout<<solution.wordBreak(s,wordDict)<<endl;
    Sleep(100);
    endTime = clock();
    cout<<"use time: "<<(double)(endTime-startTime)<<endl;
}
#endif